#include <bits/stdc++.h>
#include "caltime.cpp"
#include "read_data.cpp"
using namespace std;

// solving 
int best_ans;
int ans[MAX_n];
int cur[MAX_n];

int get(int k,int cur_c){
	double res=0;
	for(int i=k;i<n;i++){
		if(cur_c>=bag[i].w)cur_c-=bag[i].w,res+=bag[i].v;
		else {
			res+=bag[i].v*cur_c/bag[i].w;
			break;
		}
	}
	return (int)res;
}

void dfs(int k,int c_left,int cur_ans){
	if(k>=n){
		if(cur_ans>best_ans){
			best_ans=cur_ans;
			for(int i=0;i<n;i++)ans[i]=cur[i];
		}
		return ;
	}
	if(get(k,c_left)+cur_ans<=best_ans)return;
	if(c_left>=bag[k].w){
		cur[k]=1;
		dfs(k+1,c_left-bag[k].w,cur_ans+bag[k].v);
		cur[k]=0;
	}
	dfs(k+1,c_left,cur_ans); 
}

void solve(int k){
	double T=0;
	for(int i=0;i<100;i++){
		best_ans=0;
		Start();
		dfs(0,c,0);
		End();
		T+=Cal_it();
	}
	printf("data#%d :\n",k);
	printf("n: %d  c: %d \n",n,c);
	printf("answer : %d \n",best_ans);
	for(int i=0;i<n;i++)printf("%d",ans[i]);puts("");
	printf("Ave-Time: %.4lfms\n",T/100);puts("");
}

int main(){
	read_file_names();
	freopen("backtracking","w",stdout);
	for(int i=0;i<N;i++){
		read_data(i);
		solve(i); 
	}
}

